﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace Borg
{
    public class OrderedSet<T> : IList<T>, ISet<T>
    {
        private readonly List<T> _list;
        private readonly HashSet<T> _set;

        public int Count
        {
            get { return _set.Count; }
        }

        public bool IsReadOnly
        {
            get { return false; }
        }

        public T this[int index]
        {
            get { return _list[index]; }
            set
            {
                _list[index] = value;
                AssertConsistency();
            }
        }

        public OrderedSet()
        {
            _set = new HashSet<T>();
            _list = new List<T>();
        }

        public OrderedSet(IEnumerable<T> collection)
            : this()
        {
            foreach (var obj in collection)
                Add(obj);
            
            AssertConsistency();
        }

        public OrderedSet(IEqualityComparer<T> comparer)
        {
            _set = new HashSet<T>(comparer);
            _list = new List<T>();

            AssertConsistency();
        }

        public OrderedSet(IEnumerable<T> collection, IEqualityComparer<T> comparer)
            : this(comparer)
        {
            foreach (var obj in collection)
                Add(obj);
            
            AssertConsistency();
        }

        public bool Add(T item)
        {
            bool added;
            
            if (_set.Add(item))
            {
                _list.Add(item);
                added = true;
            }
            else
                added = false;

            AssertConsistency();

            return added;
        }

        void ICollection<T>.Add(T item)
        {
            if (!Add(item))
                throw new InvalidOperationException("Item is already in the ordered set");
        }

        public void Insert(int index, T item)
        {
            if (!_set.Add(item))
                throw new InvalidOperationException("Item is already in the ordered set");
            
            _list.Insert(index, item);
            AssertConsistency();
        }

        public bool Remove(T item)
        {
            var removed = _set.Remove(item);

            if (removed)
                _list.RemoveAt(InternalIndexOf(item));
            
            AssertConsistency();

            return removed;
        }

        public void RemoveAt(int index)
        {
            _set.Remove(_list[index]);
            _list.RemoveAt(index);
            AssertConsistency();
        }

        public void Clear()
        {
            _set.Clear();
            _list.Clear();
            AssertConsistency();
        }

        public bool Contains(T item)
        {
            return _set.Contains(item);
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            _list.CopyTo(array, arrayIndex);
        }

        public int IndexOf(T item)
        {
            return InternalIndexOf(item);
        }

        public T[] ToArray()
        {
            return _list.ToArray();
        }

        public IEnumerator<T> GetEnumerator()
        {
            return _list.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public void UnionWith(IEnumerable<T> other)
        {
            if (other == null)
                throw new ArgumentNullException("other");

            foreach (var obj in other)
                Add(obj);

            AssertConsistency();
        }

        public void IntersectWith(IEnumerable<T> other)
        {
            if (other == null)
                throw new ArgumentNullException("other");

            _set.IntersectWith(other);

            if (_set.Count == _list.Count)
                return;

            if (_set.Count == 0)
                _list.Clear();

            for (var i = _list.Count - 1; i >= 0; --i)
            {
                if (!_set.Contains(_list[i]))
                    _list.RemoveAt(i);
            }
            
            AssertConsistency();
        }

        public void ExceptWith(IEnumerable<T> other)
        {
            if (other == null)
                throw new ArgumentNullException("other");
            
            if (other == this)
                Clear();
            
            foreach (var obj in other)
                Remove(obj);
            
            AssertConsistency();
        }

        public void SymmetricExceptWith(IEnumerable<T> other)
        {
            if (other == null)
                throw new ArgumentNullException("other");

            var orderedSet = new OrderedSet<T>(other, _set.Comparer);

            for (var i = _list.Count - 1; i >= 0; --i)
            {
                var obj = _list[i];

                if (!orderedSet.Contains(obj))
                    continue;

                _set.Remove(obj);
                _list.RemoveAt(i);
                orderedSet.Remove(obj);
            }

            foreach (var obj in orderedSet)
                Add(obj);

            AssertConsistency();
        }

        private int InternalIndexOf(T item)
        {
            var comparer = _set.Comparer;

            for (var i = 0; i < _list.Count; ++i)
                if (comparer.Equals(item, _list[i]))
                    return i;

            return -1;
        }

        private void AssertConsistency()
        { }

        public bool IsSubsetOf(IEnumerable<T> other)
        {
            if (other == null)
                throw new ArgumentNullException("other");
            
            return _set.IsSubsetOf(other);
        }

        public bool IsSupersetOf(IEnumerable<T> other)
        {
            if (other == null)
                throw new ArgumentNullException("other");
            
            return _set.IsSupersetOf(other);
        }

        public bool IsProperSupersetOf(IEnumerable<T> other)
        {
            if (other == null)
                throw new ArgumentNullException("other");
            
            return _set.IsProperSupersetOf(other);
        }

        public bool IsProperSubsetOf(IEnumerable<T> other)
        {
            if (other == null)
                throw new ArgumentNullException("other");
            
            return _set.IsProperSubsetOf(other);
        }

        public bool Overlaps(IEnumerable<T> other)
        {
            if (other == null)
                throw new ArgumentNullException("other");
            
            return _set.Overlaps(other);
        }

        public bool SetEquals(IEnumerable<T> other)
        {
            if (other == null)
                throw new ArgumentNullException("other");
            
            return _set.SetEquals(other);
        }
    }
}
